package day04;

/**
 * 给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
 *
 * 如果可以将 x恰好 减到0 ，返回 最小操作数 ；否则，返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,4,2,3], x = 5
 * 输出：2
 * 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
 * 示例 2：
 *
 * 输入：nums = [5,6,7,8,9], x = 4
 * 输出：-1
 * 示例 3：
 *
 * 输入：nums = [3,2,20,1,1,3], x = 10
 * 输出：5
 * 解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
 *
 *
 */
//回溯思路没错可惜超时了

/**
 * public int minOperations(int[] nums, int x) {
 *         int n = nums.length;
 *         return backTracking(nums,0,n-1,x);
 *     }
 *     public int backTracking(int[] nums, int start,int end,int x){
 *         if(x<0||x==0){
 *             return x==0?0:-1;
 *         }
 *         if(start>end){
 *             return -1;
 *         }
 *         int count1=backTracking(nums,start+1,end,x-nums[start]);
 *         int count2=backTracking(nums,start,end-1,x-nums[end]);
 *         if(count1<0&&count2<0){
 *             return -1;
 *         }else if(count1<0&&count2>=0){
 *             return count2+1;
 *         }else if(count2<0&&count1>=0){
 *             return count1+1;
 *         }
 *         return count1<count2?count1+1:count2+1;
 *     }
 */
public class Solution10 {
    public int minOperations(int[] nums, int x) {
        int numSum=0;
        int n =nums.length;
        for (int i = 0; i < n; i++) {
            numSum+=nums[i];
        }
        int child=numSum-x;
        if(child==0){
            return n;
        }
        if(child<0){
            return -1;
        }
        int start=0,end=0;
        int maxLength=-1;
        int sum=0;
        while (end<n){
            sum+=nums[end];
            while (sum>child){
                sum-=nums[start];
                start++;
            }
            if(sum==child){
                maxLength=Math.max(maxLength,end-start+1);
            }
            end++;
        }
        return maxLength<0?-1:n-maxLength;
    }
}
